package com.exam.citi;

/**
 * date:
 * description:
 */
public class Solution001 {
    public static void main(String[] args) {
        int maxTime = 30;
        int[] passingFees = new int[]{5,1,2,20,20,3};
        int n = passingFees.length;
        int[][] edges = {{0,1,10},{1,2,10},{2,5,10},{0,3,1},{3,4,10},{4,5,15}};
//        int[][] edges = new int[n][n];
//        edges[0][1] = 10;
//        edges[1][2] = 10;
//        edges[2][5] = 10;
//        edges[0][3] = 1;
//        edges[3][4] = 10;
//        edges[4][5] = 15;
        Solution001 instance = new Solution001();
        int res = instance.minCostWithTimeLimited(maxTime, edges, passingFees);
        System.out.println(res);
    }

    public int res = Integer.MAX_VALUE;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * Given maxTime, edges, and passingFees, return the minimum cost to complete your journey, or -1 if you cannot complete it within maxTime minutes.
     * @param maxTime int整型 Maximum time cost (minute)
     * @param edges int整型二维数组 An 2-D Array for the edges array, and each edge denotes a road between cities x and y with minutes to travel
     * @param passingFees int整型一维数组 passing Fees aligned with edges
     * @return int整型
     */
    public int minCostWithTimeLimited (int maxTime, int[][] edges, int[] passingFees) {
        // write code here
        int n = passingFees.length;
        int[][] connections = new int[n][n];
        for (int[] edge : edges) {
            connections[edge[0]][edge[1]] = edge[2];
        }
        dfs(0, 0, 0, maxTime, connections, passingFees, new boolean[n]);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    public int dfs(int index, int fee, int time, int maxTime, int[][] edges, int[] passingFees, boolean[] visited){
        if(time > maxTime){
            return -1;
        }
        if(visited[index]){
            return -1;
        }
        visited[index] = true;
        fee += passingFees[index];
        if(fee > res){
            return -1;
        }
        if(index == passingFees.length - 1){
            return fee;
        }
        for (int i = 0; i < passingFees.length; i++) {
            int cost = edges[index][i];
            if(cost == 0 || visited[i]){
                continue;
            }
            int pathCost = dfs(i, fee, time + cost, maxTime, edges, passingFees, visited);
            if(pathCost != -1){
                res = Math.min(res, pathCost);
            }
        }
        visited[index] = false;
        return -1;
    }
}
